package sort

import (
	"fmt"
)

// merge into third array
func mergeV1(data []int, low, mid, high int) {
	i, j := low, mid+1
	tmp := make([]int, len(data))
	// copy
	for x := low; x < high+1; x++ {
		tmp[x] = data[x]
	}
	for k := i; k <= high; k++ {
		if i > mid {
			data[k] = tmp[j]
			j++
		} else if j > high {
			data[k] = tmp[i]
			i++
		} else if tmp[i] < tmp[j] {
			data[k] = tmp[i]
			i++
		} else {
			data[k] = tmp[j]
			j++
		}
	}
}
func sort(data []int) {
	mergesort(data, 0, len(data)-1)
}

// top--down
// 1.Use insertion sort for small subarrays
// 2. Test whether the array is already in order
func mergesort(data []int, low, high int) {
	if low >= high {
		return
	}
	if IsSorted(data[low : high+1]) {
		return
	}
	if high-low < 3 {
		InsertionSort(data[low : high+1])
		return
	}
	mid := (low + high) / 2
	mergesort(data, low, mid)
	mergesort(data, mid+1, high)
	mergeV1(data, low, mid, high)
}

// bottom-up
func mergesortV2(data []int, low, high int) {
	size := 2
	for size/2 < high {
		for i := 0; i <= high; i += size {
			h := i + size - 1
			if h > high {
				h = high
			}
			mid := i + size/2 - 1
			mergeV1(data, i, mid, h)
			fmt.Println(i, mid, h, data)
		}
		size = size * 2
	}
}

// merge [:mid] and [mid+1:] ordered arrays. Index 'high' is in the data
func mergeInPlace(data []int, low, mid, high int) {
	extra := make([]int, len(data))
	for i := low; i < high+1; i++ {
		extra[i] = data[i]
	}
	i := 0
	j := mid + 1
	for k := low; k < high+1; k++ {
		if i <= mid && j <= high {
			if extra[i] < extra[j] {
				data[k] = extra[i]
				i++
			} else {
				data[k] = extra[j]
				j++
			}
		} else {
			if i <= mid {
				data[k] = extra[i]
				i++
			} else {
				data[k] = extra[j]
				j++
			}
		}
	}
}
